public class PrimeNumberFinder {

    /**
     * 判断一个数是否为素数（基本方法）
     * 时间复杂度：O(√n)
     */
    public static boolean isPrimeBasic(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        // 只需要检查到sqrt(n)
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 使用埃拉托斯特尼筛法找出所有素数
     * 时间复杂度：O(n log log n)
     */
    public static boolean[] sieveOfEratosthenes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];

        // 初始化所有数为素数
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }

        // 标记非素数
        for (int i = 2; i * i <= limit; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        return isPrime;
    }

    /**
     * 使用基本方法找出所有素数
     */
    public static void findPrimesBasic(int limit) {
        System.out.println("使用基本方法查找素数...");
        long startTime = System.currentTimeMillis();

        int count = 0;
        for (int i = 1; i <= limit; i++) {
            if (isPrimeBasic(i)) {
                count++;
                System.out.printf("%-6d", i);

                if (count % 5 == 0) {
                    System.out.println();
                }
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.printf("\n共找到 %d 个素数\n", count);
        System.out.printf("基本方法耗时: %d 毫秒\n\n", endTime - startTime);
    }

    /**
     * 使用埃拉托斯特尼筛法找出所有素数
     */
    public static void findPrimesSieve(int limit) {
        System.out.println("使用埃拉托斯特尼筛法查找素数...");
        long startTime = System.currentTimeMillis();

        boolean[] isPrime = sieveOfEratosthenes(limit);

        int count = 0;
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                count++;
                System.out.printf("%-6d", i);

                if (count % 5 == 0) {
                    System.out.println();
                }
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.printf("\n共找到 %d 个素数\n", count);
        System.out.printf("筛法耗时: %d 毫秒\n\n", endTime - startTime);
    }

    /**
     * 优化的筛法 - 跳过偶数
     */
    public static boolean[] optimizedSieve(int limit) {
        if (limit < 2) return new boolean[0];

        boolean[] isPrime = new boolean[limit + 1];

        // 初始化，除了2以外的偶数都不是素数
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }

        // 单独处理2
        for (int j = 4; j <= limit; j += 2) {
            isPrime[j] = false;
        }

        // 只检查奇数
        for (int i = 3; i * i <= limit; i += 2) {
            if (isPrime[i]) {
                // 从i*i开始，步长为2*i（跳过偶数倍）
                for (int j = i * i; j <= limit; j += 2 * i) {
                    isPrime[j] = false;
                }
            }
        }

        return isPrime;
    }

    /**
     使用优化的筛法
     */
    public static void findPrimesOptimized(int limit) {
        System.out.println("使用优化的筛法查找素数...");
        long startTime = System.currentTimeMillis();

        boolean[] isPrime = optimizedSieve(limit);

        int count = 0;
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                count++;
                System.out.printf("%-6d", i);

                if (count % 5 == 0) {
                    System.out.println();
                }
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.printf("\n共找到 %d 个素数\n", count);
        System.out.printf("优化筛法耗时: %d 毫秒\n\n", endTime - startTime);
    }

    /**
     * 性能对比测试
     */
    public static void performanceTest(int limit) {
        System.out.println("=== 性能对比测试 ===");

        // 测试基本方法
        long startTime = System.currentTimeMillis();
        int count1 = 0;
        for (int i = 1; i <= limit; i++) {
            if (isPrimeBasic(i)) count1++;
        }
        long endTime = System.currentTimeMillis();
        System.out.printf("基本方法 - 素数个数: %d, 耗时: %d 毫秒\n", count1, endTime - startTime);

        // 测试筛法
        startTime = System.currentTimeMillis();
        boolean[] sieve = sieveOfEratosthenes(limit);
        int count2 = 0;
        for (int i = 2; i <= limit; i++) {
            if (sieve[i]) count2++;
        }
        endTime = System.currentTimeMillis();
        System.out.printf("筛法     - 素数个数: %d, 耗时: %d 毫秒\n", count2, endTime - startTime);

        // 测试优化筛法
        startTime = System.currentTimeMillis();
        boolean[] optimized = optimizedSieve(limit);
        int count3 = 0;
        for (int i = 2; i <= limit; i++) {
            if (optimized[i]) count3++;
        }
        endTime = System.currentTimeMillis();
        System.out.printf("优化筛法 - 素数个数: %d, 耗时: %d 毫秒\n", count3, endTime - startTime);

    }

    public static void main(String[] args) {
        final int LIMIT = 20000;

        System.out.println("查找 1~" + LIMIT + " 范围内的素数");
        System.out.println("====================================\n");

        // 使用优化的筛法输出素数（性能最好）
        findPrimesOptimized(LIMIT);

        // 性能对比测试
        performanceTest(LIMIT);

        System.out.println("\n====================================");
        System.out.println("程序执行完毕！");
    }
}